package io.tec.cloud.algorithm.c09_v20220711;

import java.util.Stack;

/**
 * 54	09_3	09	3	09排序总结、链表相关面试题	判断链表是否为回文结构"
 */
public class Code09_3_IsPalindromeList {

    /**
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome1(Node<Integer> head) {
        Node<Integer> cur = head;
        Stack<Node<Integer>> stack = new Stack<>();
        while (cur != null) {
            stack.add(cur);
            cur = cur.next;
        }
        cur = head;
        while (!stack.isEmpty()) {
            if (cur.v != stack.pop().v) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    /**
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(Node<Integer> head) {

        Node<Integer> fast = head;
        Node<Integer> slow = head;

        if (fast == null || fast.next == null) {
            return true;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Stack<Node<Integer>> path = new Stack<>();
        while (slow != null) {
            path.add(slow);
            slow = slow.next;
        }
        fast = head;
        while (!path.isEmpty()) {
            if (fast.v != path.pop().v) {
                return false;
            }
            fast = fast.next;
        }
        return true;
    }

    /**
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome3(Node head) {
        // 1、求中点（上中点）
        // 2、逆序
        // 3、还原
        return false;
    }

    static class Node<V> {
        V v;
        Node next;

        public Node(V v) {
            this.v = v;
        }
    }
}